1. Field of the Invention
The present invention generally relates to image processing apparatuses, and particularly relates to an image processing apparatus provided with a SIMD-type microprocessor.
2. Description of the Related Art
As a general image processing method applicable to binary image data, “labeling” assigns the same labels (e.g., one of the numbers in an ascending order) to contiguous feature pixels.
As methods for determining contiguity, a four-neighbor method checks the contiguity of four pixels on the top, left, right, and bottom sides of the pixel of interest, and an eight-neighbor method checks the contiguity of eight surrounding pixels inclusive of the above-identified four pixels and additional four pixels diagonally adjacent to the pixel of interest. In this specification, all the examples will be presented based on the four-neighbor method. When labeling is performed with respect to binary image data two-dimensionally arranged in memory, a pixel of interest is processed by referring to the result of processing of an adjacent pixel on the left or an adjacent pixel on the top side. With such referencing, consecutive processing is performed by scanning the binary image data in the direction toward the right (i.e., main scan direction) and in the direction toward the bottom (i.e., sub-scan direction), starting from the pixel at the top left corner. Such consecutive processing requires a lengthy processing time.
There may be a case in which two or more areas having respective, different labels (tentative labels) assigned by preceding processing are connected together (or found to be the contiguous areas) at later processing. In such a case, the values of the labels need to be updated, with the newly assigned same label value. To this end, information about connections between the tentative labels may be stored. After tentative labeling is finished with respect to all the pixels, the scanning (final labeling) of the image data may be repeated by referring to the information about connections until all the feature pixels connected together are assigned with the same label. If a plurality of areas assigned with different labels are connected indirectly, however, a large memory space may be required unless the information about connections is stored in a devised manner. Further, the information about connections between labels may be partially lost.
An SIMD-type microprocessor is capable of performing the same execution simultaneously on a plurality of data items in response to a single instruction. Because of this feature, SIMD-type microprocessors are frequently employed for the processing in which the amount of data is extremely large and data are simultaneously subjected to the same execution (e.g., image processing in a digital copier).
In normal image processing by an SIMD-type microprocessor, a plurality of processor elements (PE) are arranged in the main scan direction, so that the same execution is performed simultaneously on a plurality of data items, thereby achieving high-speed processing.
How to perform labeling as previously described is also an issue in the SIMD-type microprocessors.
Patent Document 1 provides for the SIMD processor to perform part of the tentative labeling process on image data as simultaneous parallel processing, thereby reducing the processing time required for labeling. However, there is no disclosure of a tentative labeling process applicable to the case in which binary image data is comprised of such complex patterns that a plurality of areas having different labels assigned by preceding processes later turn out to be indirectly connected.
Patent Document 2 performs a tentative labeling process with respect to two-dimensionally arranged image data by referring to tentative label values assigned to an adjacent pixel on the left and an adjacent pixel on the top side with respect to each pixel in a diagonal direction, thereby providing for an SIMD processor to perform all the tentative labeling processes on the image data as parallel processing. Since this process is performed in parallel with respect to each pixel in a diagonal direction, more PEs are necessary than the number of pixels in one line, resulting in a drop in the performance of SIMD processing. Further, like Patent Document 1, there is no disclosure of a tentative labeling process applicable to the case in which binary image data is comprised of complex patterns.    [Patent Document 1] U.S. Pat. No. 2,734,959    [patent Document 2] Japanese Patent Application Publication No. 2002-230540
Accordingly, there is a need for an image processing apparatus that allows an SIMD-type microprocessor to perform part of the tentative labeling process as parallel processing so as to reduce the processing time, thereby performing labeling effectively even with respect to binary image data comprised of complex patterns, with simple hardware such as a data controlling unit and a memory unit added to the SIMD-type microprocessor.